//
// Created by YimingCai on 27/03/2017.
//
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        for (vector<int>::size_type i = 0; i < nums.size(); ++i) {
            int tmp = nums[i];
            while (tmp != nums[tmp - 1]) {
                std::swap(tmp, nums[tmp - 1]);
                if (tmp - 1 == i)
                    break;
            }
            nums[i] = tmp;
        }
        vector<int> ret;
        for (vector<int>::size_type i = 0; i < nums.size(); ++i) {
            if (i + 1 != nums[i])
                ret.push_back(static_cast<int>(i + 1));
        }
        return ret;
    }
};


#include <gtest/gtest.h>
TEST(FindDisappearedNumbersTest, test1)
{
    Solution s = Solution();
    vector<int> v1 = {4,3,2,7,8,2,3,1};
    vector<int> t1 = s.findDisappearedNumbers(v1);
    std::sort(t1.begin(), t1.end());
    ASSERT_EQ(t1.size(), 2);
    EXPECT_EQ(t1[0], 5);
    EXPECT_EQ(t1[1], 6);
    vector<int> v2 = {2, 1};
    vector<int> t2 = s.findDisappearedNumbers(v2);
    EXPECT_EQ(0, t2.size());
}

int main(int argc, char** argv)
{
    ::testing::InitGoogleTest(&argc, argv);
    int ret = RUN_ALL_TESTS();
    return ret;
}
